package com.cwj.lab4.SORT;

import com.cwj.lab4.Tool;

/**
 * 快排
 * 小到大
 * */

public class   quickSort<T extends Comparable<T>> implements Sorted<T>{
    //内部类，用来装三向切分优化后的调整操作后的数组信息
    class Group{
        int lef,rig;//其意义是三切分数组后会有两个边界，这个两数值就是边界
        public Group(int lef, int rig) {
            this.lef = lef;
            this.rig = rig;
        }
    }
    //排序
    public void Sort(T[]nums){
        Sort(nums,0,nums.length-1);
    }
    //排序，递归
    private  void Sort(T[]nums,int lef,int rig){
        if(lef>=rig)return ;
        randomDone(nums,lef,rig);
        Group group=change(nums,lef,rig);
        Sort(nums,lef,group.lef);
        Sort(nums, group.rig,rig);
    }
    //对要选取的轴随机化
    private void randomDone(T[]nums,int lef,int rig){
        int one=lef+(int)(Math.random()*(rig-lef+1));
        Tool.swap(nums,one,lef);
    }
    //调整数组调整后的数组有三部分：小于，等于，大于
    private Group change(T[] nums,int lef,int rig){
        T data=nums[lef];
        int lefP=lef,rigP=rig,midP=lef+1;
        while(midP<=rigP){
            int t_res=nums[midP].compareTo(data);
            if(t_res<0){
                Tool.swap(nums,lefP++,midP++);
            }else if(t_res==0){
                midP+=1;
            }else{
                Tool.swap(nums,midP,rigP--);
            }
        }
        nums[lefP]=data;
        return new Group(lefP-1,rigP+1);
    }

    public static void main(String[] args) {
    }
}
